The Travelling Salesman problem (TSP) is a well-known problem in computer science. Roughly speaking, it refers to a salesperson who must deliver packages in cities that are modelled through a weighted graph, and the objective is to find the optimal route such that the total distance travelled is minimized.

This problem is known for its complexity and for the fact that it is a NP-hard problem, which means that there is no polynomial-time solution (assuming P != NP).

The problem we must solve is, in fact, a specific variant of the TSP, called Vehicle Routing Problem (VRP) which is different from the TSP inasmuch as there are now multiple salespeople (couriers). We will, in addition, add following constraints:

  • Each courier has a limited space he/she can carry

  • New orders may appear during the trips, so the

  • Order may have time-constrained pickup/delivery times: if it can't be picked up/delivered by some time, it's no use.

I can assume I'm given:

  • A reliable estimate of the time it will take a courier to go from point A to point B

  • The capacity each courier can carry at any one time (in litres) and the volume of each package.

Other things I can assume

  • Couriers may deny the order

Supposing we have to develop a quick solution just to start off with, without looking at how other people have solved this, here's what I would propose:

These are not optimal solutions. They're just initial solutions that gets the job done quickly.

Our problem can be approached like this:

Given a steady stream of new packages, how to I assign couriers to a) pick up the packages and b) deliver those packages, so as to minimize the total amount of time/distance travelled by the couriers.

Assumptions

  • I would split the city into a number of non-overlapping sectors and suppose I have some number of couriers either active or waiting in each of those sectors.

    • Let's assume that orders within those sectors are considered to be "nearby" so that, on average, adding a pickup/deliver order to a courier that's active inside that sector is considered to be acceptable

    • This also reduces the penalty that a courier incurs if he/she must pickup/deliver orders sequentially, rather than concurrently.

  • Let's assume that each courier has a delivery list, which are the next orders he/she will fulfill and, when we push an order to a courier, it means that we will add that order to the end of his/her delivery list.

    • We can also insert an order into an arbitrary place in his/her list (e.g. for time-constrained orders that must be picked-up/delivered at a given time)
  • All other things being equal, we would rather assign a new order to an active courier, so as to avoid him/her becoming inactive.

  • We need to keep a pool of waiting couriers (for orders no active courier can take) but it must be as small as possible, because it costs money to keep them waiting and, while they are waiting, they don't generate any money for us.

    • in other words, we want to be able to deliver all orders using the smallest possible amount of couriers

Version 1 (Blocking; sequential order processing)

function: get_active_couriers_by_base_sector(x)

return all active couriers who, by the end of their respective order lists, will have x as base area, with couriers with smallest order lists first

function: get_adjacent_areas(x)

return areas which are adjacent to x

for each new order o:

for each area a:

   if o is completely within area a:



      if o is NOT time-constrained:

            couriers <- get_active_couriers_by_base_area(a)

            if couriers is not empty:
                c <- couriers.get_first()
                push o to c

            else // no active couriers available in area a

                as  <- get_adjacent_areas(a)
                couriers_in_adjacent_areas <- get_active_couriers_by_base_area(as)

                if couriers_in_adjacent_areas is not empty:
                    c <- couriers_in_adjacent_areas.get_first()
                    push o to c

                else // no available active couriers even in adjacent areas       
                    c <- get_first_waiting_courier()
                    push o to c

        else // o IS time-constrained:

            candidate_couriers <- get_active_couriers_by_base_area(a)        

            if candidate_couriers is not empty         

                for each active courier c in candidate_couriers:

                    if all orders after o's pickup time are NOT time-constrained 
                        AND the state of c's trunk supports the addition of a package as large as o:
                            insert o in c's delivery list, after the first order that
                            can be picked/up delivered before o's pickup time, given the time estimates
                            and shift all other orders after that

            else: // no candidate couriers in base area a

                as <- get_adjacent_areas(a)
                candidate_couriers <- get_active_couriers_by_base_area(as) 


                if candidate_couriers is not empty         

                    for each active courier c in candidate_couriers:

                        if all orders after o's pickup time are NOT time-constrained 
                            AND the state of c's trunk supports the addition of a package as large as o:
                                insert o in c's delivery list, after the first order that
                                can be picked/up delivered before o's pickup time, given the time estimates
                                and shift all other orders after that

                else // no active couriers could be found, even in adjacent areas
                    c <- get_first_waiting_courier()
                    push o to c

else: // this order spans multiple areas

      a <- o.pickup.get_area() 

      if O is NOT time-constrained
          couriers <- get_active_couriers_by_base_area(a)

          if couriers is not empty:
                c <- couriers.get_first()
                push o to c

          else // no active couriers available in area a
                as  <- get_adjacent_areas(a)
                couriers_in_adjacent_areas <- get_active_couriers_by_base_area(as)

                if couriers_in_adjacent_areas is not empty:
                    c <- couriers_in_adjacent_areas.get_first()
                    push o to c 

                else // no available active couriers even in adjacent areas       
                    c <- get_first_waiting_courier()
                    push o to c


      else: // order IS time-constrained

            candidate_couriers <- get_active_couriers_by_base_area(a)        

            if candidate_couriers is not empty         

                for each active courier c in candidate_couriers:

                    if all orders after o's pickup time are NOT time-constrained 
                        AND the state of c's trunk supports the addition of a package as large as o:
                            insert o in c's delivery list, after the first order that
                            can be picked/up delivered before o's pickup time, given the time estimates
                            and shift all other orders after that

            else: // no candidate couriers in base area a

                as <- get_adjacent_areas(a)
                candidate_couriers <- get_active_couriers_by_base_area(as) 


                if candidate_couriers is not empty         

                    for each active courier c in candidate_couriers:

                        if all orders after o's pickup time are NOT time-constrained 
                            AND the state of c's trunk supports the addition of a package as large as o:
                                insert o in c's delivery list, after the first order that
                                can be picked/up delivered before o's pickup time, given the time estimates
                                and shift all other orders after that

                else // no active couriers could be found, even in adjacent areas
                    c <- get_first_waiting_courier()
                    push o to c



NOTES:

  • if a courier delivers an order in area B, that area becomes his BASE area for the day (unless it's changed again)

for each new order o:

a <- o.pickup.get_area()            

if o is NOT time-constrained:

    couriers <- get_active_couriers_by_base_area(a)

    if couriers is not empty:
        c <- couriers.get_first()
        push o to c

    else // no active couriers available in area a, so we try in adjacent areas

        as  <- get_adjacent_areas(a)
        couriers_in_adjacent_areas <- get_active_couriers_by_base_area(as)

        if couriers_in_adjacent_areas is not empty:
            c <- couriers_in_adjacent_areas.get_first()
            push o to c

        else // no available active couriers even in adjacent areas       
            c <- get_first_waiting_courier()
            push o to c

else // o IS time-constrained:

    candidate_couriers <- get_active_couriers_by_base_area(a)        

    if candidate_couriers is not empty         

        for each active courier c in candidate_couriers:

            if all orders after o's pickup time are NOT time-constrained 
                AND the state of c's trunk supports the addition of a package as large as o:
                    insert o in c's delivery list, after the first order that
                    can be picked/up delivered before o's pickup time, given the time estimates
                    and shift all other orders after that

    else // no active couriers available in area a, so we try in adjacent areas

        as <- get_adjacent_areas(a)
        candidate_couriers <- get_active_couriers_by_base_area(as) 

        if candidate_couriers is not empty         

            for each active courier c in candidate_couriers:

                if all orders after o's pickup time are NOT time-constrained 
                    AND the state of c's trunk supports the addition of a package as large as o:
                        insert o in c's delivery list, after the first order that
                        can be picked/up delivered before o's pickup time, given the time estimates
                        and shift all other orders after that

        else // no active couriers could be found, even in adjacent areas
            c <- get_first_waiting_courier()
            push o to c

NOTES:

  • if a courier delivers an order in area B, that area becomes his BASE area for the day (unless it's changed again)

Analysis

  • if too many couriers get too burdened by this algorithm, we can adjust the following:

    • increase the size of the areas which will probably cause larger delivery queues for each courier

    • decrease the size of the areas (smaller areas will reduce the coverage area for each courier but may increase the number of order that span multiple areas)

    • add couriers

  • in the worst case scenario, we have a time complexity of

Complexity

  • the space complexity is as follows:

    • a list of orders for each active courier - O(N)

    • a list of couriers - O(N)

Things that can go wrong

  • a courier may decide to leave with a non-empty delivery list, in which case we must re-assign those orders

    • we could just re-add those order into the stream, as if they were new orders
  • If we compare this algorithm to a processor that has to process tasks, each courier would be a processor with a single-core and no multiprocessing capabilities, i.e. it can't have two orders concurrently.

    • This means that each courier can't interleave orders (as a processor switches between processes that are doing slow tasks such as reading from disk) a courier will sit idle for a long time if we have a time-constrained order where the delivery time is hours or days after the pickup time.

    • One solution for this is, naturally, to allow each courier (core) to process multiple orders (processes) at the same time, keeping the packages (process context) in memory. We could use the same scheduling mechanisms a processor uses, and watch out for things like starvation.

Other thoughts

  • we could consider dynamic areas, instead of static ones (say a circle with radius d around the courier)

  • or we could choose better areas, after we collect some data on which areas have more orders

  • maybe we should calculate the best courier for a given order based upon where that courier will be after the delivery of the last order in his/her queue

  • Consider cases when it's best for the courier not to pickup/deliver orders sequentially

    • But pickup both orders and then deliver both of them (i.e. add some sort of concurrency)

Version 2

After looking at a couple of websites and research articles, one comes to the conclusion that, since there is no known way (other than brute forcing all possible paths) to obtain an exact answer for all but trivial problems, one can approach this in one of two ways (stimmt das?)

The vehicle routing problem: State of the art classification and review

Vehicle routing problems with loading constraints: state-of-the-art and future directions

The Vehicle Routing Problem: An overview of exact and approximate algorithms

A Tabu Search Heuristic for the Vehicle Routing Problem

Google Optimization Tools